package zuo.algo.c08;

import zuo.algo.data.graph.Graph;
import zuo.algo.data.graph.Node;
import zuo.algo.util.GraphUtils;

import java.util.*;

public class Topology {

    public static List<Node> exc1(Graph graph) {
        List<Node> res = new ArrayList<>();
        LinkedList<Node> queue = new LinkedList<>();

        Map<Node, Integer> inMap = new HashMap<>(graph.nodes.size());
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                queue.add(node);
            }
        }

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            res.add(node);
            for (Node next : node.nexts) {
                Integer in = inMap.get(next);
                if (in == null) {
                    throw new IllegalStateException();
                }
                in -= 1;
                if (0 == in) {
                    queue.add(next);
                }
                inMap.put(next, in);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][] {
                {0, 0, 0, 0},
                {1, 0, 0, 0},
                {1, 1, 0, 0},
                {0, 1, 1, 0}
        };
        Graph graph1 = GraphUtils.createGraph1(matrix);
        List<Node> res = exc1(graph1);
        System.out.println();
    }
}
